A los 30 años Carlos de Viana - ya rey titular de Navarra, impedido de reinar por su padre don Juan - tuvo amores con una doncella de su hermana Leonor llamada María de Armendáriz, hija de Arnaut, señor de Armendáriz. Se decía que ya en 1443, cinco años antes de enviudar, le había regalado un vestido.

Se conserva en la Casa de Medinaceli un billete amoroso escrito a su amada María y fechado en Artajona, en mayo de 1451, que dice:

"Yo el Príncipe do mi buena fe a vos, dona María de Armendáriz, que aviendo de vos alguna criatura o criaturas, yo vos tomaré por
mujer mía; e por ende fize aquesta de mi propia mano, firmada de mi nombre en Artaxona, a dos de mayo de mil CCCC uno. Charles"

María casó en 1457 con Francisco de Barbastro, secretario de Carlos de Viana.

Tuvo con María una hija llamada Ana ("la señorica"). El Príncipe la reconoce como heredera única y legítima del Reyno de Navarra en un testamento ológrafo fechado en Zaragoza el 20 de abril de 1453, al salir de prisión. En el testamento se ordenaba que por tal se la reconociese y proclamase en la muy noble y muy leal ciudad de Pamplona.

Ana casó con Luis de la Cerda, 5º conde de Medinaceli (+ 1501) tras haber éste repudiado a su esposa Catalina Laso de la Vega, hija del Marqués de Santillana, don Diego Hurtado de Mendoza. El conde de Medinaceli tratará de conseguir su "derecho" en la sucesión de Navarra que decía "pertenecer legítimamente" a la condesa doña Ana de Navarra, su mujer, hija del príncipe don Carlos. Mostró Ana (con su padrastro Francisco de Barbastro) el testamento de su padre a Fernando el Católico para hacer valer sus derechos. Pero el rey Fernando no quiso escucharles.

Cuando estuvo el Príncipe en Mallorca encendió amores con Margarita Colom, de la que no solía hablar y a la que dejó "prenyada". Cuenta Jaime del Burgo que según el historiador mallorquín Gabriel Verd Martorell, fruto de estos amores nació Cristóbal Colón, el descubridor de América. Margarita era hija de Juan Colom quien había estado al servicio de Renato de Anjou y residía en el Municipio de Felanitx en una finca llamada Alquería Roja, actualmente San Ramonet. El hijo de Margarita pudo nacer en la primavera de 1460. Dice el historiador que dado que el Príncipe no se preocupaba de mantener en secreto sus otros amores, no se comprende su empeño en ocultar la identidad de este nuevo hijo natural que le atribuye el historiador mallorquín.

Es demasiado fantástico para ser real el que la razón de aquel ocultamiento fuese el origen chueta (judío) de Margarita, lo que para un príncipe tan cristiano como don Carlos hubiera sido un descrédito. En aquellos tiempos tener un hijo medio judío hubiera sido un serio problema. Si las cosas hubieran sido así, Cristóbal Colón hubiera sido entonces sobrino bastardo de Fernando el Católico y todos los misterios con que el propio descubridor ocultó su origen se explicarían de esta manera.

No se puede dar credibilidad a esta hipótesis. Y hay buenas razones para ello.

Colón falleció en Valladolid el 20 de mayo de 1506. De haber sido hijo de Margarita, hubiera tenido entonces unos 46 años. Sin embargo Fernando el Católico firma una cédula el 23 de febrero de 1505 en la que califica de anciano a Colón:

En la fecha de su muerte Colón tenía 70 años, luego debió haber nacido hacia 1436, mucho antes del embarazo de Margarita en Mallorca. Por otro lado, el Príncipe no tiene a este niño por heredero en su testamento del día de su muerte.

Que el Príncipe tuviera amores con Margarita y la dejara embarazada, podría ser cierto a la vista de la carta que escribió el Príncipe y que, según el historiador francés Georges Desdevises, envió al gobernador de Mallorca el 29 de octubre de 1459, carta que se conserva en el Archivo de la Corona de Aragón en Barcelona:

“agradecemos vos muy mucho lo que fecho haveys en recomendación de Margarita.
La verdad de la cosa mostrará lo que haver sentido de ella ser prenyada.”

¿Llegó a nacer este niño?. ¿Nació y murió enseguida de nacer?. No se sabe. Pero este es el texto que da pié a la hipotética filiación de Cristóbal Colón. Recientemente se ha puesto de manifiesto que esta carta se dirigió al Virrey de Sicilia Lope Ximenis de Urrea, por lo que se trataba de otra Margarita llamada Cappa.

Tuvo también el Príncipe amores encendidos con otra hermosa dama llamada Brianda Vaca cuando estuvo en Nápoles. Allí le había nacido de ella un hijo llamado Felipe que sería con el tiempo conde de Beaufort. Fue éste nombrado obispo electo de Palermo y renunciaría más tarde a esa dignidad por el Maestrazgo de Montesa. Al servicio de su tío Fernando el Católico, acabaría sus días en julio de 1488 en Baza, de una piedra de espingarda que le alcanzó la boca.

Brianda acompañó a Carlos de Viana hasta el final y se encontraba con él en Barcelona en el momento de su muerte en septiembre de 1461. Los catalanes le instaron a que casara con Brianda in articulo mortis para legitimar a su hijo Felipe y declararlo sucesor. Pero don Carlos comprendió que la herencia que le iba a dejar sería muy pesada para aquél niño y sólo serviría para continuar las luchas fratricidas. Por ello prefirió nombrar a su hermana la infanta Blanca como su legítima sucesora, tal como habían dispuesto su abuelo Carlos III "el Noble" y su madre Blanca I de Navarra Evreux.

Otro de los amores del Príncipe, menos citado por los historiadores, fue el que tuvo por Guiomar de Sayas, gentil damisela que estuvo a su servicio.

De su estancia en Sicilia se conoce a Juan Alonso de Navarra y Aragón, hijo habido en 1459 por el Príncipe en una doncella - “de baja esfera, aunque de singular hermosura” - a quien se conoce con el nombre de Margarita Cappa. Había nacido en Palermo en 1459. Este hijo llegó a ser abad de San Juan de la Peña y más tarde (octubre 1484) obispo de Huesca, Jaca y Barbastro. Sixto IV expidió la bula de nombramiento el 21de mayo de 1477. La bula de Inocencio VIII que le nombraba obispo de Huesca está expedida el 1 de octubre de 1484. Falleció el 13 de diciembre de1526.